The present invention generally relates to input-dependent computation of inverse transformations used in decoding block-based, compressed digital video bitstreams. With the advancement in information theory in the latter half of this century, the transmission of image and video data has become possible in digital formats over low bandwidth channels. Information theory allows digital video to be systematically compressed such that the size of the compressed bitstream is much less than the original with some sacrifice in the form of distortion from the original data. In order for any decoder to be able to reconstruct video frames from a compressed bitstream, the format of the bitstream must be known to the decoder. Standardization is one way to ensure that a bitstream is decoded correctly by different decoders. In most well known digital video compression standards, such as MPEG-1, MPEG-2, MPEG-4, H.261, and H.263, a compression scheme called hybrid motion-compensated block-based video coding is employed.
The method a decoder performs for the above standards may be summarized as follows. A frame of video is broken down into a smaller unit called block which is normally 8.times.8 pixels in size. For each frame of video being encoded at a particular time, each block of data is decoded by finding a prediction of the current block via motion compensation using a motion vector decoded from the bitstream and the previously decoded video frame. Then, transform coefficients are obtained by decompressing and dequantizing a portion of the compressed data that corresponds to the current block. The next tasks involve computing an inverse transformation to get coefficients that represent the intensity level of pixels in the block. The resulting block is added back to the predicted block in the first step, and become a new reconstructed block. In all of the standards mentioned, the Discrete Cosine Transform (DCT) and its inverse (IDCT) are used to obtain and reverse the transform coefficients. This transform is used because it provides good compression performance with the possibility for effective hardware implementation. Furthermore, the two-dimensional IDCT is a separable transform, i.e. it may be performed repetitively by one-dimensional IDCT operations applied for all rows (row-wise IDCT) and then for all columns (column-wise IDCT), or vice versa. This reduces the complexity and size of a program used to implement the transform.
For a decoder, the IDCT is an essential component requiring exact performance to avoid drift between encoder and decoder. This is a result of the predictive nature of video coding. Since the transformation must be performed on every coded block and involves a considerable amount of arithmetic computation, it is considered as one of the major computationally intense tasks in video decoding systems. There have been several approaches to computing the DCT and IDCT in an efficient manner. Those techniques involve exploiting trigonometric properties of the transform to remove redundant computations. Their goal is to minimize the complexity regardless of the content of the input, e.g. they assume that all DCT coefficients are non-zero. Algorithms that have input-dependent complexity are also known. The input-dependency is achieved by performing classification of the input block of DCT coefficients, and applying different operations needed for the IDCT based on the class of the block. For example, a block may be classified into an "all-zero" block when all of the DCT coefficients in the block are zero, a "DC-only" block when only the (0,0)-th DCT coefficients are non-zero, "4.times.4-DCT" block when only 16 coefficients in the low 4.times.4 DCT frequency components are non-zero, and "8.times.8-DCT" for any other cases. These methods do not use any information from the decoded bitstream to classify the block of DCT coefficients before performing the IDCT, but rather, they test the value of all coefficients directly. This may be very inefficient in certain cases.
Based on the lack of sufficient methods for performing fast video decoding with low complexity, a need exists for a method and a device to improve the performance of a block-based video decoder which may exploit the properties of the decoded bitstream to reduce the complexity of performing an inverse DCT transformation. This transformation is the most commonly performed operation in the decoder.